{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Tree Serialization（二叉树的序列化）][1]\n",
    "\n",
    "[1]: https://mp.weixin.qq.com/s/g2xEaY3ZxEP8d823aJnZwg\n",
    "\n",
    "> You are given the root of a binary tree. You need to implement 2 functions:\n",
    ">\n",
    "> 1. `serialize(root)` which serializes the tree into a string representation.\n",
    "> 2. `deserialize(s)` which deserializes the string back to the original tree that it represents. \n",
    ">\n",
    "> &emsp;&emsp;For this problem, often you will be asked to design your own serialization format. However, for simplicity, let's use the pre-order traversal of the tree.\n",
    "\n",
    "> &emsp;&emsp;给定一棵二叉树的根节点，实现2个函数/方法：\n",
    ">\n",
    "> 1. `serialize`函数，用于将树序列化为字符串表示；\n",
    "> 2. `deserialize`函数，用于将字符串表示反序列化为原本的树。\n",
    ">\n",
    "> &emsp;&emsp;对于这个问题，一般情况下需要你自己设计字符串表示。然而，为了简单起见，让我们用二叉树的前序遍历作为序列化字符串。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Starting Point（模板代码）\n",
    "\n",
    "**Notice:** Algorithms will be coded in the template directly.\n",
    "\n",
    "【注意】算法将直接编写在样板代码中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Class Definition（类定义）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        ''' The Constructor '''\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def __str__(self):\n",
    "        ''' Pre-order Traversal '''\n",
    "        result = ''\n",
    "        result += str(self.value)\n",
    "        if self.left:\n",
    "            result += str(self.left)\n",
    "        if self.right:\n",
    "            result += str(self.right)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Seairalization（序列化）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def serialize(root: Node) -> str:\n",
    "    ''' Recursive Algorithm '''\n",
    "    if root is None:\n",
    "        return '#'\n",
    "    else:\n",
    "        return (\n",
    "            str(root.value) + ' ' +\n",
    "            serialize(root.left) + ' ' +\n",
    "            serialize(root.right)\n",
    "        )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Desialization（反序列化）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "source": [
    "#### Iterative（迭代算法）\n",
    "\n",
    "Accroding to my collaborator [@mjd507][1]'s words, he said that most of the people can express a recursive solution, especially in those problems with *Tree Structure*. So in his *JavaScript* version solution, he usually use iterative solution instead of recursive one.\n",
    "\n",
    "However, in *tree construction* problem, it's too complicated for developers to code an iterative solution.\n",
    "\n",
    "This iterative solution was coded on my own. It should be collapsed and invisible because of my settings on *JupyterLab*. If it appeard accidentally and you can't understand what I'm doing in this algorithm, just give up and look for the next recursive one.\n",
    "\n",
    "&emsp;&emsp;听我的存储库协作者[@mjd507][1]说，“几乎所有的人都能写出递归算法，尤其是在那些与**树**结构相关的题目中”。所以在他的JavaScript版题解中，他一般会选用迭代算法而不是递归算法。\n",
    "\n",
    "&emsp;&emsp;然而，在**生成树**问题中，迭代算法对于开发者们来说太复杂了。\n",
    "\n",
    "&emsp;&emsp;这个迭代算法是我自己编写的。由于我在**Jupyter Lab**上的设定，所以它应该是被折叠、隐藏起来了。如果它意外地显示了出来可你看不懂我在干什么，还是原地放弃查看后续的递归算法吧。\n",
    "\n",
    "[1]: https://github.com/mdj507"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "def deserialize_iterativly(data: str) -> Node:\n",
    "    # Split all elements into a list. \n",
    "    data = data.split(' ')\n",
    "\n",
    "    # Create a stack to generate a binary tree.\n",
    "    stack = []\n",
    "\n",
    "    # Define an index pointer.\n",
    "    index = 0\n",
    "\n",
    "    # Keep in loop until return operation.\n",
    "    while True:\n",
    "        # Push elements into the stack and prevent IndexError.\n",
    "        if index < len(data):\n",
    "            stack.append(data[index])\n",
    "            index += 1\n",
    "\n",
    "        # When there's only a Node element in the stack,\n",
    "        # return it.\n",
    "        if len(stack) == 1 and type(stack[0]) == Node:\n",
    "            return stack[0]\n",
    "\n",
    "        # If an element has no subtrees, convert it into Node.\n",
    "        if len(stack) >= 3 and stack[-2:] == ['#', '#']:\n",
    "            stack = stack[:len(stack) - 2]\n",
    "            stack[-1] = Node(stack[-1])\n",
    "\n",
    "        # If an element has both left and right subtrees,\n",
    "        # upgrade it to a newer tree.\n",
    "        if (len(stack) >= 3 and type(stack[-2]) == Node\n",
    "            and type(stack[-1]) == Node):\n",
    "            subtrees = stack[-2:]\n",
    "            stack = stack[:len(stack) - 2]\n",
    "            stack[-1] = Node(stack[-1], subtrees[-2], subtrees[-1])\n",
    "\n",
    "        # If an element only has a right subtree, ...\n",
    "        if (len(stack) >= 3 and stack[-2] == '#'\n",
    "            and type(stack[-1]) == Node):\n",
    "            subtrees = stack[-1]\n",
    "            stack = stack[:len(stack) - 2]\n",
    "            stack[-1] = Node(stack[-1], right=subtrees)\n",
    "\n",
    "        # If an element only has a left subtree, ...\n",
    "        if (len(stack) >= 3 and type(stack[-2]) == Node\n",
    "            and stack[-1] == '#'):\n",
    "            subtrees = stack[-2]\n",
    "            stack = stack[:len(stack) - 2]\n",
    "            stack[-1] = Node(stack[-1], left=subtrees)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Recursive（递归算法）\n",
    "\n",
    "Split the `string` with *seperator* (which you defined in `serialize()` function, in this case, a white space `' '`) into a `list`. We regard and operate it as a `queue`. Because we serialize the tree in a pre-order way, we can deserialize it in the same way.\n",
    "\n",
    "1. Take the element from the head of the queue. \n",
    "2. If it's not `'#'`, we create a node which based on it (as the root). \n",
    "3. Construct its left subtree recursivly from the queue first, then its right subtree.\n",
    "4. When we meet a `'#'`, just return `None`.\n",
    "\n",
    "将**字符串**以分隔符（你之前在`serialize()`函数中定义的，在这个例子中就是空格）切分为列表，并将这个它视为**队列**进行数据操作。因为我们是以前序遍历地形式将其序列化的，我们也能以相同的方式将其反序列化。\n",
    "\n",
    "1. 从队列中提取首元素；\n",
    "2. 如果它不是`'#'`，我们创建一个新节点（当作根节点）并以它作为节点的值；\n",
    "3. 从队首提取元素递归创建它的左子树，然后是右子树；\n",
    "4. 当我们遇到`'#'`，返回`None`即可。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def deserialize_recursivly(data: str) -> Node:\n",
    "    array = iter(data.split(' '))\n",
    "\n",
    "\n",
    "    def _recursive():\n",
    "        ''' A local recursive function '''\n",
    "        item = next(array)\n",
    "        if item == '#':\n",
    "            return None\n",
    "        root = Node(item, _recursive(), _recursive())\n",
    "        return root\n",
    "\n",
    "\n",
    "    return _recursive()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Cases（测试样例）\n",
    "\n",
    "```text\n",
    "#     1\n",
    "#    / \\\n",
    "#   3   4\n",
    "#  / \\   \\\n",
    "# 2   5   7\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 3 2 # # 5 # # 4 # 7 # #'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "serialize(\n",
    "    Node(\n",
    "        1,\n",
    "        Node(\n",
    "            3,\n",
    "            Node(2),\n",
    "            Node(5)\n",
    "        ),\n",
    "        Node(\n",
    "            4,\n",
    "            None,\n",
    "            Node(7)\n",
    "        )\n",
    "    )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true,
     "source_hidden": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'132547'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deserialize_iterativly('1 3 2 # # 5 # # 4 # 7 # #').__str__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'132547'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deserialize_recursivly('1 3 2 # # 5 # # 4 # 7 # #').__str__()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
